package mysql;

import java.sql.SQLException;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;



public class Dijkstra {
	
	private DB db;
	

    /**
     * The set of nodes for which the shortest distance to the source
     * has been found.
     */
	private final Set<Integer> settledNodes;
	
    /**
     * The currently known shortest distance for all nodes.
     */
	private final Map<Integer, Integer> shortestDistances;
	
	
	/**
     * Predecessors list: maps a nodes to its predecessor in the spanning tree of
     * shortest paths.
     */
	private final Map<Integer, Integer> predecessors;
	
	/**
     * Infinity value for distances.
     */
    public static final int INFINITE_DISTANCE = Integer.MAX_VALUE;
	
    /**
     * This comparator orders nodes according to their shortest distances,
     * in ascending fashion. If two cities have the same shortest distance,
     * we compare the cities themselves.
     */
    private final Comparator<Integer> shortestDistanceComparator = new Comparator<Integer>()
        {
            public int compare(Integer left, Integer right)
            {
                // note that this trick doesn't work for huge distances, close to Integer.MAX_VALUE
                int result = getShortestDistance(left) - getShortestDistance(right);
                
                return (result == 0) ? left.compareTo(right) : result;
            }


        };
	
    /**
     * Some value to initialize the priority queue with.
     */
    private static final int INITIAL_CAPACITY = 1000;
        
    /**
     * The working set of cities, kept ordered by shortest distance.
     */
    private final PriorityQueue<Integer> unsettledNodes = new PriorityQueue<Integer>(INITIAL_CAPACITY, shortestDistanceComparator);
	
	public Dijkstra(){
		db = new DB("jdbc:mysql://localhost/mysql_db", "root", "password");
		settledNodes = new HashSet<Integer>();
		predecessors = new HashMap<Integer, Integer>();
		shortestDistances = new HashMap<Integer, Integer>();
	}
	

    private void init(int start)
    {
        settledNodes.clear();
        unsettledNodes.clear();
        
        shortestDistances.clear();
        predecessors.clear();
        
        // add source
        setShortestDistance(start, 0);
        unsettledNodes.add(start);
    }
	
	private boolean isSettled(int v)
	{
	    return settledNodes.contains(v);
	}
	
	private void setPredecessor(int a, int b)
	{
	    predecessors.put(a, b);
	}

	public int getPredecessor(int node)
	{
	    return predecessors.get(node);
	}
	
    public int getShortestDistance(int node)
    {
        Integer d = shortestDistances.get(node);
        return (d == null) ? INFINITE_DISTANCE : d;
    }
    
    /**
	 * Set the new shortest distance for the given node,
	 * and re-balance the queue according to new shortest distances.
	 * 
	 * @param node the node to set
	 * @param distance new shortest distance value
	 */        
    private void setShortestDistance(int node, int distance)
    {
        /*
         * This crucial step ensures no duplicates are created in the queue
         * when an existing unsettled node is updated with a new shortest 
         * distance.
         * 
         * Note: this operation takes linear time. If performance is a concern,
         * consider using a TreeSet instead instead of a PriorityQueue. 
         * TreeSet.remove() performs in logarithmic time, but the PriorityQueue
         * is simpler. (An earlier version of this class used a TreeSet.)
         */
        unsettledNodes.remove(node);

        /*
         * Update the shortest distance.
         */
        shortestDistances.put(node, distance);
        
		/*
		 * Re-balance the queue according to the new shortest distance found
		 * (see the comparator the queue was initialized with).
		 */
		unsettledNodes.add(node);        
    }

	
    /**
	 * Compute new shortest distance for neighboring nodes and update if a shorter
	 * distance is found.
	 * 
	 * @param u the node
     * @throws SQLException 
	 */
    private void relaxNeighbors(int u) throws SQLException
    {
        for (int v : db.getNeighbors(u))
        {
            // skip node already settled
            if (isSettled(v)) continue;
            
            // the weight of each edge is the same, 1
            int shortDist = getShortestDistance(u) + 1;
            
            if (shortDist < getShortestDistance(v))
            {
            	// assign new shortest distance and mark unsettled
                setShortestDistance(v, shortDist);
                                
                // assign predecessor in shortest path
                setPredecessor(v, u);
            }
        }        
    }

    
    /**
     * Run Dijkstra's shortest path algorithm on the database.
     * The results of the algorithm are available through
     * {@link #getPredecessor(node)}
     * and 
     * {@link #getShortestDistance(node)}
     * upon completion of this method.
     * 
     * @param start the starting node
     * @param destination the destination node. If this argument is <code>null</code>, the algorithm is
     * run on the entire graph, instead of being stopped as soon as the destination is reached.
     * @throws SQLException 
     */
    public void execute(int start, int destination) throws SQLException
    {
        init(start);
        
        // the current node
        Integer u;
        
        // extract the node with the shortest distance
        while ((u = unsettledNodes.poll()) != null)
        {
            assert !isSettled(u);
            
            // destination reached, stop
            if (u == destination) break;
            
            settledNodes.add(u);
            
            relaxNeighbors(u);
        }
    }
    
 // testing
 	public static void main(String[] args) throws SQLException {
 		Dijkstra dj = new Dijkstra();
 		dj.execute(1, 52);
 		int distance = dj.getShortestDistance(52);
 		if(distance == dj.INFINITE_DISTANCE){
 			System.out.println("Shortest distance: no path between nodes");
 		}
 		else {
 			System.out.println("Shortest distance: " + distance);
 		}
 		
 	}


}
